﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _04_Graph
{
   class TrieNode
   {
      public int pass;
      public int end;
      public TrieNode[] nexts;

      public TrieNode()
      {
         pass = 0;
         end = 0;
         nexts = new TrieNode[26];  // a - z
      }
   }

   class Trie
   {
      private TrieNode root;

      public Trie() { root = new TrieNode(); }

      public void Add(string str)
      {
         TrieNode p = root;
         p.pass++;
         for (int i = 0; i < str.Length; i++)
         {
            int cur = str[i] - 'a';
            // 新结点，需要创建
            if (p.nexts[cur] == null)
               p.nexts[cur] = new TrieNode();
            p = p.nexts[cur];
            p.pass++;
         }
         p.end++;
      }

      public int Find(string str)
      {
         TrieNode p = root;
         int cur = 0, i = 0;
         for (i = 0; i < str.Length; i++)
         {
            cur = str[i] - 'a';
            if (p.nexts[cur] != null)
            {
               p = p.nexts[cur];
            }
            else break;
         }
         return i != str.Length ? 0 : p.end;
      }

      // 找前缀
      public int PreFixNumber(string str)
      {
         TrieNode p = root;
         int cur = 0;
         for (int i = 0; i < str.Length; i++)
         {
            cur = str[i] - 'a';
            // 找到了后续道路
            if (p.nexts[cur] != null)
               p = p.nexts[cur];
            // 找不到后续道路
            else return 0;
         }
         return p.pass;
      }

      // 删除
      public void Delete(string str)
      {
         // 必须满足存在该字符串
         if (Find(str) != 0)
         {
            TrieNode p = root;
            p.pass--;
            int cur = 0;
            for (int i = 0; i < str.Length; i++)
            {
               cur = str[i] - 'a';
               if (--p.nexts[cur].pass == 0)
               {
                  p.nexts[cur] = null;
                  return;
               }
               p = p.nexts[cur];
            }
            p.end--;
         }
      }
   }
}
